#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

int calculateMinimumHP(vector<vector<int>>& dungeon)
{
    int n = dungeon.size(), m = dungeon[0].size();
    vector<vector<int>> f(n + 1, vector<int>(m + 1, INT_MAX));
    f[n][m - 1] = 1, f[n - 1][m] = 1;
    for (int i = n - 1; i >= 0; i--)
        for (int j = m - 1; j >= 0; j--)
            f[i][j] = max(1, min(f[i + 1][j], f[i][j + 1]) - dungeon[i][j]);
    return f[0][0];
}

int minCost(vector<vector<int>>& costs) {
    int n = costs.size();
    vector<vector<int>> f(n + 1, vector<int>(3));
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = min(f[i - 1][1], f[i - 1][2]) + costs[i - 1][0];
        f[i][1] = min(f[i - 1][0], f[i - 1][2]) + costs[i - 1][1];
        f[i][2] = min(f[i - 1][1], f[i - 1][0]) + costs[i - 1][2];
    }
    return min(f[n][0], min(f[n][1], f[n][2]));
}

const int INF = 0x3f3f3f3f;
int maxProfit(int k, vector<int>& prices) {
    int n = prices.size();
    k = min(k, n / 2);
    vector<vector<int>> f(n, vector<int>(k + 1, -INF)), g(n, vector<int>(k + 1, -INF));
    f[0][0] = -prices[0], g[0][0] = 0;
    for (int i = 1; i < n; i++)
        for (int j = 0; j < k + 1; j++)
        {
            f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
            g[i][j] = g[i - 1][j];
            if (j - 1 >= 0)  g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
        }

    int res = 0;
    for (int i = 0; i <= k; i++)   res = max(res, g[n - 1][i]);
    return res;
}